The present invention relates to semiconductor devices for carrying out primality determination, and in particular relates to techniques effective in protection from side channel attacks to encryption or the like.
The encryption key used for encryption is often generated based on a prime number. For example, in generating a public key and a private key of RSA encryption, two large prime numbers need to be generated. Two prime numbers need to be kept in secret because if these two prime numbers leaked, the calculation of the private key from the public key is easy.
The prime number generation is usually carried out by the following method. First, a random number is generated, and then the primality of the random number is checked by primality determination, such as a Fermat test, a Miller-Rabin test, and a Solovay-Strassen test (Non-Patent Document 1; Alfred J. Menezes and Paul C. van Oorschot and Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC Press, Chapter 4—Public Key Parameters, October 1996). Usually, the primality determination includes power residue calculation (modular exponentiation calculation, modulo exponentiation calculation). For example, when the primality determination of an integer P is carried out based on the Fermat test, an integral random number A is selected and power residue AP−1 mod P is calculated.
According to Euler's theorem, when N is a positive integer and A and N are positive integers relatively prime to each other, Aφ(N) mod N=1 (Exp. 1) is established. Here, φ is the Euler function. When P is a prime number, φ(P)=P−1 and it is guaranteed that the result of the power residue calculation A(P−1) mod P is one.
Because a prime number is relatively rare, the determination of many prime number candidates is often carried out until a prime number is found. For the reason of efficiency, when a prime number candidate fails in the primality determination, this prime number candidate is preferably incremented.
Because a prime number at the time of generation of an RSA encryption key is important for security of an encryption system, the prime number is a target for potential attack, such as side channel analysis, in which during power residue calculation in the primality determination, the power consumption caused by generation of a prime number is measured and the value of the prime number is leaked using a pattern of the power consumption. Because in the incremental prime number generation, the power residue calculation targeted for mutually close integers (P, P+2, P+4, etc.) is executed, the risk of such an attack is amplified.